#ifndef DIFF_H_
#define DIFF_H_

#include <vector>

namespace lxj
{
// 航班预订统计
// 这里有 n 个航班，它们分别从 1 到 n 进行编号。
// 有一份航班预订表 bookings ，
// 表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi]
// 意味着在从 firsti 到 lasti
// （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
// 请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。
// 测试链接 : https://leetcode.cn/problems/corporate-flight-bookings/
inline std::vector<int> corpFlightBookings(std::vector<std::vector<int>>& bookings, int n)
{
    std::vector<int> ans(n + 2, 0);
    for (auto& booking : bookings) {
        ans[booking[0]] += booking[2];
        ans[booking[1] + 1] -= booking[2];
    }

    for (int i = 1; i < ans.size(); i++) {
        ans[i] += ans[i - 1];
        ans[i - 1] = ans[i];
    }
    ans.resize(n);
    return ans;
}

// 有m个数组
//  一开始1~n范围上的数字都是0，一共有m个操作，每次操作为(l,r,s,e,d)
//  表示在l~r范围上依次加上首项为s、末项为e、公差为d的数列
//  m个操作做完之后，统计1~n范围上所有数字的最大值和异或和
//  测试链接 : https://www.luogu.com.cn/problem/P4231
inline std::vector<int> lrsed(std::vector<std::vector<int>> bookings, int n)
{
    if (bookings.empty()) return std::vector<int>{};
    auto set = [](std::vector<int>& vi, int l, int r, int s, int e, int d) {
        vi[l] += s;
        vi[l + 1] += d - s;
        vi[r + 1] -= d + e;
        vi[r + 2] += e;
    };

    std::vector<int> ans(n + 3);
    for (auto& booking : bookings) {
        set(ans, booking[0], booking[1], booking[2], booking[3], booking[4]);
    }

    for (int i = 1; i < ans.size(); i++) {
        ans[i] += ans[i - 1];
    }

    for (int i = 1; i < ans.size(); i++) {
        ans[i] += ans[i - 1];
        ans[i - 1] = ans[i];
    }
    ans.resize(n);
    return ans;
}

// 一群人落水后求每个位置的水位高度
// 问题描述比较复杂，见测试链接
// 测试链接 : https://www.luogu.com.cn/problem/P5026
class FallWater {
    // 题目说了m <= 10^6，代表湖泊宽度
    // 这就是MAX的含义，湖泊最大宽度的极限
    inline static int MAX = 1000001;

    // 数值保护，因为题目中v最大是10000
    // 所以左侧影响最远的位置到达了x - 3 * v + 1
    // 所以右侧影响最远的位置到达了x + 3 * v - 1
    // x如果是正式的位置(1~m)，那么左、右侧可能超过正式位置差不多30000的规模
    // 这就是OFFSET的含义
    inline static int OFFSET = 30001;
    // inline static int OFFSET = 9;

    // 湖泊宽度是MAXN，是正式位置的范围
    // 左、右侧可能超过正式位置差不多OFFSET的规模
    // 所以准备一个长度为OFFSET + MAX + OFFSET的数组
    // 这样一来，左侧影响最远的位置...右侧影响最远的位置，
    // 都可以被arr中的下标表示出来，就省去了很多越界讨论
    // 详细解释看set方法的注释
    inline static std::vector<int> arr = std::vector<int>(OFFSET + MAX + OFFSET);
    // std::vector<int> arr = std::vector<int>(28);

    inline void fall(int v, int x)
    {
        int d = v / ((x - 2 * v) - (x - 3 * v));
        set(x - 3 * v + 1, x - 2 * v, d, v, d);
        set(x - 2 * v + 1, x, v - d, -v, -d);
        set(x + 1, x + 2 * v, -v + d, v, d);
        set(x + 2 * v + 1, x + 3 * v, v - d, 0, -d);
    }

    inline void set(int l, int r, int s, int e, int d)
    {
        arr[l + OFFSET] += s;
        arr[l + OFFSET + 1] += d - s;
        arr[r + OFFSET + 1] -= d + e;
        arr[r + OFFSET + 2] += e;
    }

    inline void build()
    {
        for (int i = 1; i < arr.size(); i++) {
            arr[i] += arr[i - 1];
        }
        for (int i = 1; i < arr.size(); i++) {
            arr[i] += arr[i - 1];
        }
    }

public:
    inline std::vector<int> operator()(const std::vector<int>& manVolums,
                                       const std::vector<int>& pointWateres,
                                       int                     width)
    {
        for (int i = 0; i < manVolums.size(); i++) {
            fall(manVolums[i], pointWateres[i]);
        }
        build();
        auto ans = std::vector<int>(arr.data() + OFFSET + 1, arr.data() + OFFSET + 1 + width);
        std::fill(arr.begin(), arr.end(), 0);
        return ans;
    }
};

}   // namespace lxj

#endif